from typing import List,Set
from collections import deque

'''
    找图中起点到终点的最短距离
'''

class Node:
    def __init__(self,val) -> None:
        self.val = val
        self.neighbors = []

    def BFS(start,target):
        q = deque()
        visited = set()   # 避免走回头路
        q.append(start)  # 将起点加入队列
        visited.add(start)

        step = 0 # 记录扩散的步数

        while q:
            step += 1
            size = len(q)
            # 将当前队列中的所有节点向四周扩散
            for i in range(size):
                cur = q.popleft()

                #判断是否到达终点
                if cur == target:
                    return step
                
                # 将cur相邻节点加入队列
                for x in cur.neighbors:
                    if x not in visited:
                        q.append(x)
                        visited.add(x)
            
        # 如果走到这里，说明在图中没有找到目标节点
        return -1

            

